/**
 * https://leetcode-cn.com/problems/maximum-product-subarray/
 * 乘积最大子数组
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * @param nums
 */
const maxProduct = (nums: number[]): number => {
  let maxF = nums[0],
    minF = nums[0],
    ans = nums[0];

  // dp[i] 表示下标i的最大乘积
  const len = nums.length;
  for (let i = 1; i < len; i++) {
    let max = maxF,
      min = minF;

    // 维护最大值, 负数 * 负数可能乘积更大
    maxF = Math.max(nums[i], min * nums[i], max * nums[i]);

    // 维护最小值 负数 * 正数可能乘积更大
    minF = Math.min(nums[i], min * nums[i], max * nums[i]);

    ans = Math.max(maxF, ans);
  }

  return ans;
};
